/**
 * 
 */
package net.sf.graph4j.algorithm.graph.maxflow;

import net.sf.graph4j.element.graph.Edge;
import net.sf.graph4j.element.graph.Graph;
import net.sf.graph4j.element.graph.Vertex;

/**
 * The intuition behind the push-relabel method is probably best understood in
 * terms of fluid flows: we consider a flow network G = (V, E) to be a system of
 * interconnected pipes of given capacities. Applying this analogy to the
 * Ford-Fulkerson method, we might say that each augmenting path in the network
 * gives rise to an additional stream of fluid, with no branch points, flowing
 * from the source to the sink. The Ford-Fulkerson method iteratively adds more
 * streams of flow until no more can be added.
 * 
 * The generic push-relabel algorithm has a rather different intuition. As
 * before, directed edges correspond to pipes. Vertices, which are pipe
 * junctions, have two interesting properties. First, to accommodate excess
 * flow, each vertex has an out-flow pipe leading to an arbitrarily large
 * reservoir that can accumulate fluid. Second, each vertex, its reservoir, and
 * all its pipe connections are on a platform whose height increases as the
 * algorithm progresses.
 * 
 * Vertex heights determine how flow is pushed: we only push flow downhill, that
 * is, from a higher vertex to a lower vertex. The flow from a lower vertex to a
 * higher vertex may be positive, but operations that push flow only push it
 * downhill. The height of the source is fixed at |V|, and the height of the
 * sink is fixed at 0. All other vertex heights start at 0 and increase with
 * time. The algorithm first sends as much flow as possible downhill from the
 * source toward the sink. The amount it sends is exactly enough to fill each
 * outgoing pipe from the source to capacity; that is, it sends the capacity of
 * the cut (s, V - s). When flow first enters an intermediate vertex, it
 * collects in the vertex's reservoir. From there, it is eventually pushed
 * downhill.
 * 
 * It may eventually happen that the only pipes that leave a vertex u and are
 * not already saturated with flow connect to vertices that are on the same
 * level as u or are uphill from u. In this case, to rid an overflowing vertex u
 * of its excess flow, we must increase its height-an operation called
 * "relabeling" vertex u. Its height is increased to one unit more than the
 * height of the lowest of its neighbors to which it has an unsaturated pipe.
 * After a vertex is relabeled, therefore, there is at least one outgoing pipe
 * through which more flow can be pushed.
 * 
 * Eventually, all the flow that can possibly get through to the sink has
 * arrived there. No more can arrive, because the pipes obey the capacity
 * constraints; the amount of flow across any cut is still limited by the
 * capacity of the cut. To make the preflow a "legal" flow, the algorithm then
 * sends the excess collected in the reservoirs of overflowing vertices back to
 * the source by continuing to relabel vertices to above the fixed height |V| of
 * the source. As we shall see, once all the reservoirs have been emptied, the
 * preflow is not only a "legal" flow, it is also a maximum flow.
 * 
 * @author palomino
 * 
 */
public class PushRelabelMaxFlow extends AbstractPushRelabelMaxFlow {

	/**
	 * 
	 */
	public PushRelabelMaxFlow() {
		super();
		// TODO Auto-generated constructor stub
	}
	
	public void findFlow(Graph g, Vertex source, Vertex sink) {
		
		assert (g.contains(source) && g.contains(sink));
		this.source = source;
		this.sink = sink;
		this.g = g;
		
		initPreFlow(g, source);
		
		boolean operated = true;
		while (operated) {
			
			operated = false;
			
			for (Edge e : g.getEdges()) {
				if (canPush (e)){
					push (e);
					operated = true;
				}
				
				if (canReversePush(e)) {
					reversePush(e);
					operated = true;
				}
			}
			
			for (Vertex v : g.getVertices()) {
				if (canRelabel(v)){
					reLabel (v);
					operated = true;
				}
			}
		}
	}
}
